Longest Substring Without Repeating Characters || Longest Palindromic Substring

发表于

Longest Substring Without Repeating Characters

Question

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

Analysis

该题要求的是返回最长不含重复字符的子串的长度，所以没有必要保存各个符合条件的子串，只需设置变量maxlength记录子串的最大长度即可。同时设置hashset用以判断是否遇到重复字符。

从第一个字符开始遍历，不重复字符加入hashset，当遇到重复字符时，首先通过对比hashset和maxlength的大小来确定是否需要更新，然后从start开始清除hashset中无用的字符直到遇到第一个重复的字符停止，注意这时候需要多清除一位，因为重复的字符还没有被清除。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int size=s.length();
        if(size==0||size==1||s==null){
            return s.length();
        }
        HashSet<Character> test=new HashSet<Character>();
        int start=0;
        int max=0;
        StringBuilder result=new StringBuilder();
        for(int i=0;i<size;i++){
            if(!test.contains(s.charAt(i))){
                test.add(s.charAt(i));
            }
            else{
                max=Math.max(test.size(),max);
                while(s.charAt(start)!=s.charAt(i)){
                    test.remove(s.charAt(start));
                    start++;
                }
                start++;
            }
        }
        max = Math.max(max, test.size());
        return max;
    }
}

Longest Palindromic Substring

Question

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Analysis

除了暴力解决找出所有子串再判断是否为回文子串之外，可以以每一个字符为中心，同时向左右挪动指针，知道两遍的字符不相同，不是回文为止。当发现不是回文的时候，记录当前字符串长度(end-begin+1)并与maxlength比较查看是否需要更新。最后返回从begin到begin+maxlength的字符串即可。

  • 查看回文字符串的时候有两种情况，字符个数分为偶数和奇数。
  • 循环中begin需要从0开始，>=
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    public String longestPalindrome(String s) {
        int size=s.length();
        int maxlength=0;
        int start=0;
        
        if(size==1||size==0)
            return s;
        
        for(int i=0;i<size;i++){//odd
             int begin=i-1,end=i+1;
             while(begin>=0&&end<size&&s.charAt(begin)==s.charAt(end)){
                 if(end-begin+1>maxlength){
                     maxlength=end-begin+1;
                     start=begin;
                 }
                 begin--;
                 end++;
             }
        }
        
        for(int j=0;j<size;j++){//even
            int begin=j,end=j+1;
            while(begin>=0&&end<size&&s.charAt(begin)==s.charAt(end)){
                if(end-begin+1>maxlength){
                     maxlength=end-begin+1;
                     start=begin;
                 }
                begin--;
                end++;
            }
        }
        if(maxlength>0)
            return s.substring(start,start+maxlength);
        return null;
    }
}